# Copyright (c) 2010
# The Regents of the University of Michigan
# All Rights Reserved

# Permission is granted to use, copy, create derivative works, and
# redistribute this software and such derivative works for any purpose,
# so long as the name of the University of Michigan is not used in
# any advertising or publicity pertaining to the use or distribution
# of this software without specific, written prior authorization. If
# the above copyright notice or any other identification of the
# University of Michigan is included in any copy of any portion of
# this software, then the disclaimer below must also be included.

# This software is provided as is, without representation or warranty
# of any kind either express or implied, including without limitation
# the implied warranties of merchantability, fitness for a particular
# purpose, or noninfringement.  The Regents of the University of
# Michigan shall not be liable for any damages, including special,
# indirect, incidental, or consequential damages, with respect to any
# claim arising out of or in connection with the use of the software,
# even if it has been or is hereafter advised of the possibility of
# such damages.

'''Items of general use in implementing DHT support.'''

import event

import array
import collections
import itertools
import random
import socket


HACK_DISABLE_TIMER = True

class RateLimitedQueue(object):
  '''A queue of actions, limited at a.

  Intended concept is global to the whole process, but it's
  conceivable that there might be multiple queues, one for each class
  of actions that should be rate-limited, although there's currently
  no mechanism for arbitrating among them (e.g., by priority) if
  necessary.
  '''

  def __init__(self, actions_per_sec, threshold, max_secs_under_threshold):
    self.actions_per_sec = actions_per_sec
    self.threshold = threshold
    self.max_secs_under_threshold = max_secs_under_threshold

    self.send_queue = collections.deque()
    self.send_count = 0
    self.send_timer_event = None
    self.consec_secs_under_threshold = 0
    self.send_slowed_callback = None

  def update_threshold_counter(self, count_last_sec):
    if count_last_sec <= self.threshold:
      self.consec_secs_under_threshold += 1
      if self.consec_secs_under_threshold > self.max_secs_under_threshold:
        self.consec_secs_under_threshold = 0
        self.send_queue.clear()
        self.send_slowed_callback()
    else:
      self.consec_secs_under_threshold = 0

  def _handle_send_timer(self):
    if self.send_queue:
      amount_to_send = min(len(self.send_queue),
                           self.actions_per_sec - self.send_count)
      for _ in xrange(amount_to_send):
        send_obj, args = self.send_queue.pop()
        send_obj._actually_send(*args)
      self.send_count += amount_to_send

    # Reschedule unconditionally so that we can halt properly.
    self.update_threshold_counter(self.send_count)
    self.send_count = 0
    return True

  def exec_or_enqueue(self, send_obj, args):
    '''Execute send_func now or enqueue it to be sent later.

    send_func is enqueued iff there are other requests waiting or we are over
    the quota of sends this second already.
    '''
    sq = self.send_queue
    if not sq and self.send_count < self.actions_per_sec:
      send_obj._actually_send(*args)
      self.send_count += 1
      if self.send_timer_event is None and not HACK_DISABLE_TIMER:
        self.send_timer_event = event.timeout(1, self._handle_send_timer)

      # No *change* in timer status; queue may have transitioned to full
      # or it may remain empty.
    else: # Get in line.
      sq.append((send_obj, args))


_SENDS_PER_SEC = 3000
the_send_queue = RateLimitedQueue(_SENDS_PER_SEC, 0, 30)


class BaseClient(object):
  '''Basic DHT client.

  Abstract base class.
  Supports throttling outgoing traffic and the basic Kademlia RPCs.

  Implementations should promise to call the appropriate
  handle_foo_{request,reply} message for each incoming packet.
  '''

  def __init__(self, address, send_queue=the_send_queue):
    self.address = address
    self.send_queue = send_queue

    self.sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    self.sock.bind(('', address[1]))
    event.read(self.sock, self._handle_recv)

  def _actually_send(self, packet, address, *args):
    # "protected", meant to be reused in subclasses.
    try:
      self.sock.sendto(packet, address)
    except socket.error as e:
      if e.errno not in (1, 13, 22): # Ignore EINVAL and EPERM
        print 'failed sending %s to %s' % (packet.encode('hex'), address)
        raise
      else:
        print 'error %d sending to %s' % (e.errno, address)

  def _send(self, *args):
    # "protected", meant to be reused in subclasses.
    self.send_queue.exec_or_enqueue(self, args)

  def _handle_recv(self):
    raise NotImplementedError()

  def handle_ping_request(self, *args):
    pass

  def handle_store_request(self, *args):
    pass

  def handle_find_node_request(self, *args):
    pass

  def handle_ping_reply(self, *args):
    pass

  def handle_find_node_reply(self, *args):
    pass

  def handle_find_value_reply(self, *args):
    pass

  def handle_store_reply(self, *args):
    pass

  def send_ping_request(self, other_address, *args):
    raise NotImplementedError()

  def send_stats_request(self, other_address, *args):
    raise NotImplementedError()

  def send_ping_reply(self, other_address, *args):
    raise NotImplementedError()

  def send_store_request(self, other_address, *args):
    raise NotImplementedError()

  def send_store_reply(self, other_address, *args):
    raise NotImplementedError()

  def send_find_node(self, other_address, id_to_find, *args):
    raise NotImplementedError()


_LEADING_ZEROS = array.array('b',(8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4,
4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))


try:
  from cvuze_util import compute_shared_prefix_bits
except ImportError as e:
  print 'couldn\'t import compute_shared_prefix_bits:', e
  def compute_shared_prefix_bits(id1, id2):
    shared_bits = 0
    for (c1, c2) in itertools.izip(id1, id2):
      if c1 == c2:
        shared_bits += 8
      else:
        # Leading zeros in x ^ y are the shared bits in x and y.
        return shared_bits + _LEADING_ZEROS[(ord(c1) ^ ord(c2))]
    return shared_bits


try:
  from cvuze_util import compute_id_distance
except ImportError as e:
  print 'couldn\'t import compute_id_distance:', e
  def compute_id_distance(id1, id2):
    raw_distance = ''.join(chr(ord(x) ^ ord(y))
                           for (x, y) in itertools.izip(id1, id2))
    ret = int(raw_distance.encode('hex'), 16)
    return ret


def fast_get_closest_id(ids_list, target_id):
  '''Find the index of the closest ID in ids_list to the target ID.
  ids_list must be sorted in lexicographic order.
  '''
  import cvuze_util
  closest_id_idx = bisect.bisect(ids_list, target_id)

  if closest_id_idx == len(ids_list):
    closest_id_idx -= 1
  elif closest_id_idx and closest_id_idx != len(ids_list) - 1:
    next_shared_bits = cvuze_util.compute_shared_prefix_bits(
      target_id, ids_list[closest_id_idx])
  
    prev_shared_bits = cvuze_util.compute_shared_prefix_bits(
        target_id, ids_list[closest_id_idx-1])

    if prev_shared_bits > next_shared_bits:
      closest_id_idx -= 1

  return closest_id_idx


def fake_brute_force_id_with_bits(ip_addresses, desired_prefix, nbits,
                                  have_root=False):
  return desired_prefix + '\x00' * (20 - len(desired_prefix)), random.randint(1024, 65535)


def intify(node_id):
  return long(node_id.encode('hex'), 16)
